class Solution {
public:
    bool wordBreak(string s, unordered_set<string> &dict) {
        if(s.empty())
            return false;
        if(dict.empty())
        return false;

        vector<bool> temp(s.size()+1,false);
        temp[0]=true;

        for(int i=1;i<=s.size();i++)
        {
            for(int j=i-1;j>=0;j--)
            {
                //
                if(temp[j]&&dict.find(s.substr(j,i-j))!=dict.end())
                {
                    temp[i]=true;
                    break;
                }
            }
        }

        return temp[s.size()];

        
    }
};
